<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="UTF-8" />
		<meta http-equiv="X-UA-Compatible" content="IE=edge" />
		<meta name="viewport" content="width=device-width, initial-scale=1.0" />
		<title>双向链表</title>
	</head>
	<body>
		<script>
			function DoublyLinkedList() {
				// 内部的类: 节点类
				function Node(data) {
					this.data = data;
					this.prev = null;
					this.next = null;
				}
				// 属性
				this.head = null;
				this.tail = null;
				this.length = 0;

				// 常见的操作：方法（其实无非就是增删改查之类的操作）
				// 1. append(data) 向链表尾部添加一个新的节点
				DoublyLinkedList.prototype.append = function (data) {
					let newNode = new Node(data);
					// 判断添加的是否是第一个节点
					if (this.head == null) {
						this.head = newNode;
						this.tail = newNode;
					} else {
						this.tail.next = newNode;
						newNode.prev = this.tail;
						this.tail = newNode;
					}
					this.length++;
				};

				// 将链表转换成字符串形式
				// 2.1 toString()
				DoublyLinkedList.prototype.toString = function () {
					return this.backwardString();
				};
				// 2.2 forwardString() 从后向前遍历
				DoublyLinkedList.prototype.forwardString = function () {
					let current = this.tail;
					let resultString = '';
					while (current) {
						resultString += current.data + ' ';
						current = current.prev;
					}
					return resultString;
				};
				// 2.3 backwardString() 从前向后遍历
				DoublyLinkedList.prototype.backwardString = function () {
					let current = this.head;
					let resultString = '';
					while (current) {
						resultString += current.data + ' ';
						current = current.next;
					}
					return resultString;
				};

				// 3. insert(position, data) 在链表的特定位置插入节点
				DoublyLinkedList.prototype.insert = function (position, data) {
					// 1. 越界判断
					if (position < 0 || position > this.length) return false;
					// 2. 根据 data 创建节点
					let newNode = new Node(data);
					// 3. 判断原来的链表是否为空
					if (this.length == 0) {
						this.head = newNode;
						this.tail = newNode;
					} else {
						if (position == 0) {
							// 3.1 判断 position 是否为 0
							this.head.prev = newNode;
							newNode.next = this.head;
							this.head = newNode;
						} else if (position == this.length) {
							// 3.2 判断插入的位置是否是最后一个位置
							this.tail.next = newNode;
							newNode.prev = this.tail;
							this.tail = newNode;
						} else {
							// 3.3 插入位置在中间
							let current = this.head;
							// let previous = null;
							let index = 0;
							while (index++ < position) {
								// previous = current;
								current = current.next;
							}
							// 修改四个指针的指向
							newNode.next = current;
							newNode.prev = current.prev;
							current.prev.next = newNode;
							current.prev = newNode;
						}
					}
					this.length++;
					return true;
				};

				// 4. get(position) 获取相应位置的元素
				DoublyLinkedList.prototype.get = function (position) {
					// 越界判断
					if (position < 0 || position >= this.length) return null;

					// let index = 0;
					// let current = this.head;
					// while (index++ < position) {
					// 	current = current.next;
					// }
					// return current.data;

					// 刚刚这样写的话，一直都是从前往后遍历，效率不高，来改进一下
					// this.length / 2 > position 从前往后遍历
					// this.length / 2 < position 从后往前遍历

					if (position < this.length / 2) {
						let current = this.head;
						let index = 0;
						while (index++ < position) {
							current = current.next;
						}
						return current.data;
					} else if (position > this.length / 2) {
						let current = this.tail;
						let index = this.length - 1;
						while (index-- > position) {
							current = current.prev;
						}
						return current.data;
					}
				};

				// 5. indexOf(data) 返回元素在链表中的索引，如果没有该元素则返回-1
				DoublyLinkedList.prototype.indexOf = function (data) {
					let current = this.head;
					let index = 0;
					while (current) {
						if (current.data == data) {
							return index;
						} else {
							current = current.next;
							index++;
						}
					}
					return -1;
				};

				// 6. update(position, newData) 修改某个位置的元素
				DoublyLinkedList.prototype.update = function (position, newData) {
					if (position < 0 || position >= this.length) return false;
					// let current = this.head;
					// let index = 0;
					// while (index++ < position) {
					// 	current = current.next;
					// }
					// let num = current.data;
					// current.data = newData;
					// // 返回修改前元素的值
					// return num;

					// 还是和 get 一样的效率问题，下面来改进一下
					if (position < this.length / 2) {
						let current = this.head;
						let index = 0;
						while (index++ < position) {
							current = current.next;
						}
						current.data = newData;
						return true;
					} else if (position > this.length / 2) {
						let current = this.tail;
						let index = this.length - 1;
						while (index-- > position) {
							current = current.prev;
						}
						current.data = newData;
						return true;
					}
				};

				// 7. removeAt(position) 从链表的特定位置删除一项, 返回删除元素的值
				DoublyLinkedList.prototype.removeAt = function (position) {
					// 1. 越界判断
					if (position < 0 || position >= this.length) return null;
					// 2. 逻辑判断
					// 2.1 判断是否只有一个节点
					let current = this.head;
					if (this.length == 1) {
						this.head = null;
						this.tail = null;
					} else {
						// this.length > 1 的情况（也就是节点不止一个的情况）
						if (position == 0) {
							// 2.2 判断删除的是否是第一个节点
							this.head.next.prev = null;
							this.head = this.head.next;
						} else if (position == this.length - 1) {
							current = this.tail;
							// 2.3 判断删除的是否是最后一个节点
							this.tail.prev.next = null;
							this.tail = this.tail.prev;
						} else {
							// 2.4 删除的是中间的节点
							let index = 0;
							while (index++ < position) {
								current = current.next;
							}
							current.prev.next = current.next;
							current.next.prev = current.prev;
						}
					}
					this.length--;
					return current.data;
				};

				// 8. remove(data) 从链表中删除特定节点
				DoublyLinkedList.prototype.remove = function (data) {
					let index = this.indexOf(data);
					return this.removeAt(index);
				};

				// 9. isEmpty() 判断链表是否为空，为空返回 true，非空返回 false
				DoublyLinkedList.prototype.isEmpty = function () {
					return this.length == 0;
				};

				// 10. size() 获取链表长度
				DoublyLinkedList.prototype.size = function () {
					return this.length;
				};

				// 11. getHead()
				DoublyLinkedList.prototype.getHead = function () {
					return this.head.data;
				};

				// 12. getTail()
				DoublyLinkedList.prototype.getTail = function () {
					return this.tail.data;
				};
			}

			// 测试代码
			// 1. append(data)
			let list = new DoublyLinkedList();
			list.append('I');
			list.append('am');
			list.append('your');
			list.append('daddy');

			// 2. 转字符串方法
			// alert(list.backwardString());
			// alert(list.forwardString());
			// alert(list.toString());

			// 3. insert(position, data)
			list.insert(0, 'oh,');
			list.insert(5, '~~~');
			list.insert(4, 'dear');
			alert(list); // oh, I am your dear daddy ~~~

			// 4. get(position)
			// alert(list.get(0));
			// alert(list.get(5));
			// alert(list.get(10));

			// 5. indexOf(data)
			// alert(list.indexOf('oh,'));
			// alert(list.indexOf('daddy'));

			// 6. update(position, newData)
			alert(list.update(5, 'father'));
			alert(list);

			// 7. removeAt(position)
			list.removeAt(0);
			alert(list);
			list.removeAt(5);
			alert(list); // I am your dear father

			// 8. remove(data)
			list.remove('dear');
			alert(list);

			// 9. isEmpty()
			alert(list.isEmpty());

			// 10. size()
			alert(list.size());

			// 11 & 12. getHead()  getTail()
			alert(list.getHead());
			alert(list.getTail());
		</script>
	</body>
</html>
